package Sort;

import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{ 1,2,3, 4, 5,};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i] + "  ");
    }
    public static void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = partition(A, p, r);
            quickSort(A, p, q - 1);
            quickSort(A, q + 1, r);
        }
    }
    public static int partition(int[] A, int p, int r) {
        int random = randInt(p, r);
        int tmp=A[r];
        A[r]=A[random];
        A[random]=tmp;
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                i += 1;
                tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }
        }
        tmp = A[r];
        i += 1;
        A[r] = A[i];
        A[i] = tmp;
        return i;
    }
    public static int randInt(int min, int max) {
        Random rand = new Random();
        int randomNum = rand.nextInt((max - min) + 1) + min;
        return randomNum;
    }
}
